package com.algomypractice.linkedlist;

import com.sourcestruct.linearlist.SingleLinkedList;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: ZhouBert
 * @date: 2019/6/5
 * @description: 单链表反转
 */
public class SingleLinkedReverse {

	public static void main(String[] args) {
		//末节点
		SingleLinkedList lastnode = new SingleLinkedList(1, null);
		SingleLinkedList nodea = new SingleLinkedList(2, lastnode);
		SingleLinkedList nodeb = new SingleLinkedList(3, nodea);
		SingleLinkedList nodec = new SingleLinkedList(4, nodeb);
		SingleLinkedList noded = new SingleLinkedList(5, nodec);
		System.out.println(noded);
		//SingleLinkedList4Hero node = reverseByArray(noded);
		//SingleLinkedList4Hero node = reverseByPoint(noded);
		///SingleLinkedList4Hero node = reverseByRecursive2(noded);
		///System.out.println(node);
		printreverseByRecursive(noded);
	}

	/**
	 * 通过数组实现单链表反转（O(n)）
	 *
	 * @param node
	 * @return
	 */
	public static SingleLinkedList reverseByArray(SingleLinkedList node) {
		//1.借助数组的空间存储单链表
		List<Integer> arr = new ArrayList<>();
		while (node != null) {
			arr.add(node.getData());
			node = node.getNext();
		}
		//2.利用数组逆向组装链表
		SingleLinkedList root = new SingleLinkedList(arr.get(arr.size() - 1));
		//设置引用
		SingleLinkedList tempNode = root;
		for (int i = arr.size() - 2; i >= 0; i--) {
			tempNode.setNext(new SingleLinkedList(arr.get(i)));
			//让引用指向下一个节点
			tempNode = tempNode.getNext();
		}
		return root;
	}

	/**
	 * 移动指针完成单链表反转（精髓在于指针的移位）
	 *
	 * @param node
	 * @return
	 */
	public static SingleLinkedList reverseByPoint(SingleLinkedList node) {
		SingleLinkedList curr = node, pre = null;
		while (curr != null) {
			//定义下一个节点
			SingleLinkedList next = curr.getNext();
			curr.setNext(pre);
			pre = curr;
			curr = next;
		}
		return pre;
	}

	/**
	 * 通过递归
	 *
	 * @return
	 */
	public static SingleLinkedList reverseByRecursive(SingleLinkedList node) {
		if (node == null || node.getNext() == null) {
			return node;
		} else {
			SingleLinkedList newNode = reverseByRecursive(node.getNext());
			node.getNext().setNext(node);
			node.setNext(null);
			return newNode;
		}

	}

	public static SingleLinkedList reverseByRecursive2(SingleLinkedList node) {
		if (node == null || node.getNext() == null) {
			return node;
		} else {
			SingleLinkedList newNode = reverseByRecursive2(node.getNext());
			node.getNext().setNext(node);
			node.setNext(null);
			return newNode;
		}

	}

	/**
	 * 单向链表逆序输出(发现还是不能很成功就写出递归)
	 * @param node
	 */
	public static SingleLinkedList printreverseByRecursive(SingleLinkedList node){
		if (node==null){
			return node;
		}else if(node.getNext()==null) {
			System.out.print(node.getData()+",");
			return node;
		}else {
			SingleLinkedList newNode = printreverseByRecursive(node.getNext());
			node.getNext().setNext(node);
			node.setNext(null);
			System.out.print(node.getData()+",");
			return newNode;
		}
	}

	/**
	 * 反转 当前节点node 与 node.next (废弃)
	 *
	 * @param node
	 * @return
	 */
	private static SingleLinkedList recursive(SingleLinkedList node) {
		//下一节点
		SingleLinkedList next = node.getNext();
		next.setNext(node);
		return next;
	}

}
